package com.shuyan.base.algorithm;

import javax.jws.soap.SOAPBinding;
import javax.xml.stream.events.EndDocument;
import java.lang.reflect.Array;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.Arrays;

//排序算法
public class Sorting {


    public static void main(String[] args) {
        int[] price = new int[]{9, 8, 5, 6, 11};
        Sorting sorting = new Sorting();
        //sorting.bubbleSort(price);
        //selectionSort(price);
        //System.out.println(Arrays.toString(price));
        qsorting(price,0,4);
        System.out.println(Arrays.toString(price));
    }

    //冒泡排序
    public void bubbleSort(int[] array) {
        //外循环是需要比较的趟数
        //第一次外循环结束，最后面一个元素是最大的
        int temp;
        for (int i = 0; i < array.length - 1; i++) {
            //内循环是每趟要比较的次数
            for (int j = 0; j < array.length - i; j++) {
                //temp存放两个数中较大的一个
                //如果前面的元素比后面的元素大，则交换两元素的值
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    //选择排序
    public static void selectionSort(int[] array) {
        int temp, min = 0;
        for (int i = 0; i < array.length - 1; i++) {
            //假设最小值是array[i]
            min = i;
            //循环查找最小值
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            //min不等于i，假设错误，最小值不是i，而是最新的min的数值
            if (min != i) {
                temp = array[min];
                //交换假设的最小值和实际的最小值，将最小值排到前面去
                array[min] = array[i];
                array[i] = temp;
            }
        }

    }
    //快速排序法
public static void qsorting(int[] array,int start, int end){
    int pivot=array[start];
    int i=start;
    int j=end;
    while(i<j){
        while(i<j&&array[j]>pivot){
            j--;
        }
        while(i<j&&array[i]<pivot){
            i++;
        }
        if(array[i]==array[j]){
            i++;
        }else{
            int temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }

    }
    if(i-1>start){
        qsorting(array,start,i-1);
    }
    if(j+1<end){
        qsorting(array,j+1,end);
    }


}





}

